package top.fengleifeng.question;

import com.sun.tools.internal.jxc.ap.Const;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import top.fengleifeng.util.Constants;
import top.fengleifeng.util.TreeNode;

/**
 * @program: leetcode-test
 * @description: 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 * <p>
 * 例如输入：
 * <p>
 *      4    /   \   2     7  / \   / \ 1   3 6   9 镜像输出：
 * <p>
 *      4    /   \   7     2  / \   / \ 9   6 3   1
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]  
 * <p>
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 1000
 * <p>
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: fengleifeng
 * @create: 2020-08-07 16:42
 **/
public class Y剑指Offer34二叉树中和为某一值的路径 {

    /**
     * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int
     * x) { val = x; } }
     */
    class Solution {

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            if (root == null) {
                return new ArrayList<>();
            }
            List<List<Integer>> result = new LinkedList<>();
            List<Integer> list = new LinkedList<>();
            int countNow = 0;
            getval(result, sum, list, root, countNow);
            return result;
        }

        private boolean getval(List<List<Integer>> result, int sum, List<Integer> oneList, TreeNode root,
            int nowCount) {
            oneList.add(root.val);
            nowCount += root.val;
            if (root.left == null && root.right == null) {
                if (nowCount == sum) {
                    result.add(new LinkedList<>(oneList));
                    return true;
                } else {
                    int index = oneList.size() - 1;
                    oneList.remove(index);
                    return false;
                }
            } else {
                if (root.left != null) {
                    boolean getval = getval(result, sum, oneList, root.left, nowCount);
                    if (getval) {
                        oneList.remove(oneList.size() - 1);
                    }
                }
                if (root.right != null) {
                    boolean getval = getval(result, sum, oneList, root.right, nowCount);
                    if (getval) {
                        oneList.remove(oneList.size() - 1);
                    }
                }
                return true;
            }
        }
    }

    public static void main(String[] args) {
        //[1,-2,-3,1,3,-2,null,-1]
        TreeNode one = new TreeNode(1);
        one.left = new TreeNode(-2);
        one.right = new TreeNode(-3);

        one.left.left = new TreeNode(1);
        one.left.right = new TreeNode(3);

        one.right.left = new TreeNode(-2);

        one.left.left.left = new TreeNode(1);
        List<List<Integer>> lists = new Y剑指Offer34二叉树中和为某一值的路径().new Solution().pathSum(one, 2);
        Constants.pringtLinkedList(lists);
    }
}
